导航菜单

CSP202203

CSP202203_3

目录CSP202203_3题目思路Code

题目

计算资源调度器

思路

直接模拟,画个大致的分析图即可理清题目要求。

一个区上有多个节点,一个应用有多个任务。

一个任务只占用一个节点,多个任务可在一个节点上进行。

三种要求:

任务\(\in\)区任务\(\in\)区 && 区上有特定应用的任务任务\(\notin\) 节点 && 节点上有特定应用的任务

确定一系列任务,选择其最佳运行的节点。

确定维护的一定是节点的信息(因为所有操作都在节点上进行)。

考虑节点本身,首先应记录其自身编号,所属的区。

基于上述三种要求以及选择标准,我们还要记录节点运行任务总数、节点的所有任务所属应用。

使用 unordered_map 记录每个节点(具体原因后述)。

总体上就是分别针对三种需求,在所有节点中依次剔除不符合要求的节点,最后根据标准进行排序及选择。

一些问题

关于unordered_map:一开始直接采用的 map 维护,但结果是75pts(TLE),借鉴了其他人写这道题的方法,使用 unordered_map 即可AC。

unordered_map因为不要求有序,因此使用哈希表维护,而map使用的是红黑树,显然数据量与操作很多时,unordered_map要快上不少

最后的排序问题,通过自定义比较函数,只能拿到80pts(TLE),而类似处理中,他人博客通过重载运算符,使用 lambda 语句作为比较函数,则可AC。具体原因不太确定,感觉可能是涉及到STL的一些底层实现?望dalao指点

关于迭代器的删除操作:vector 等序列性容器与 map 等关联性容器在删除迭代器指向内容后迭代器的变化是不同的,这次一定记住。

在最初模拟时,样例最后一个点总是错误,最终确定是在第三个要求的函数实现错误:

函数参数传递的只是vec而不是其引用。如果传引用,在进行第三步判断时,可能会导致vec1变空。

但实际若vec2由于非必须要求而可以不为空,所供选择的节点为为进行第三步判断的vec1,此处就会产生错误,将任务误判为无节点可用。

Code

80pts(直接按注释替换sort的比较部分即可AC)

#include#include using namespace std;inline int read(){int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch >'9'){if(ch == '-') f = -1;ch = getchar();}while(ch >= '0' && ch

相关推荐: